{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style=\"text-align: center;font-size: 33px;font-weight:bold;\"> <span style=\"color:DarkGoldenrod\">&lt;&lt; 算法 &gt;&gt;</span></p>\n",
    "<p style=\"text-align: center;font-size: 25px;font-weight:bold;\"> <span style=\"color:Goldenrod\">&lt;&lt; Algorithm &gt;&gt;</span></p>\n",
    "<p style=\"text-align: right; font-size:15px; font-weight:normal\">----`*程序设计*`的_**灵魂**_</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### 1. 算法的由来\n",
    " #### 1.1 科学发展的需要\n",
    " 例如：如何计算圆周率$\\pi$与自然对数的底$\\mathit{e}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#if defined(_MSC_VER) // Make MS math.h define M_PI \n",
    "#define _USE_MATH_DEFINES \n",
    "#elif __GNUC__ \n",
    "#define _GNU_SOURCE \n",
    "#endif\n",
    "#include <stdio.h>\n",
    "#include <math.h>\n",
    "int main() {\n",
    "printf(\"%e\\n\",M_PI);\n",
    "printf(\"%e\\n\",M_E);\n",
    "return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2 工程技术的需要\n",
    "例如：二进制数的提出（为计算机电子电路设计的理论依据)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "void bin(unsigned int n,unsigned int nc){\n",
    "if(n>1) bin(n/2,nc);\n",
    "printf(\"%d\",n%2);\n",
    "if(n==nc) printf(\"\\n\");\n",
    "}\n",
    "int main(){\n",
    "bin(8,8);\n",
    "bin(9,9);\n",
    "bin(121,121);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从专业的角度上说。要掌握好C语言，特别需要了解**二进制数**在计算机中的**存储`、`排列**方式！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "又例如：行车导航中，确定到达目的地的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.3 经济运作的需要\n",
    "例如：确定公司的产品组合，在有限的资源下获取最大的经济利益"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 极大化：$\\sum_i^n a_i x_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "满足： $\\sum_i^n c_i x_i \\le b_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 算法的分类\n",
    "#### 2.1 数值计算类算法\n",
    "比计算机本身要古老得多，人类文明发展过程中遇到的各种数值计算问题，其通用解法均课归于此类<br>\n",
    "例如： 自然对数$\\mathit{e}$与圆周率$\\pi$的计算方法<br>\n",
    "#### 2.2 信息处理类算法（互联网时代的主要算法构成）\n",
    "* 对结构化信息（数据）进行处理（例如：学生信息的增、删、改、查）\n",
    "* 对非结构化信息（数据）进行处理（例如：搜索引擎（Google,Baidu））\n",
    "* 对信息进行加密、解密 （目的：提高信息的安全性）\n",
    "* 对视频、图像数据进行压缩、解压缩（目的：降低网络传输、数据存储的负担\n",
    "* 网络数据的拆分、传递、组合（目的：形成互联网）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3 人工智能类算法（`AI`:Artifical Intellience）（人类社会已经半只脚踏入了人工智能时代！）\n",
    "最终目标： 我们希望计算机、机器人能够像人类一样听、说、读、写、看、玩、思考<br>\n",
    "已经落地的产品：\n",
    "* 各类语音助手（微软、苹果、谷歌）\n",
    "* 电子商务中的个性化推荐（亚马逊、京东、阿里巴巴）\n",
    "* 运货机器人（京东，阿里巴巴，亚马逊）\n",
    "* 自动驾驶（特斯拉，谷歌，百度）\n",
    "* 对弈软件（浪潮天梭，Google DeepMind：Alpha GO！）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 算法的作用\n",
    "#### 3.1 程序=数据+算法\n",
    "#### 3.2 满足文化、科技、经济发展需求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 算法的形成与表达\n",
    "1. 确定问题并找到问题的**解决方法**\n",
    "2. 确定算法的各个步骤，以`自然语言`进行表达\n",
    "3. 绘制**算法流程图**（掌握:传统流程图;了解：BS流程图）\n",
    "4. 书写**伪代码**（符号$\\rightarrow$的含义？）\n",
    "5. 正式使用计算机语言进行**编程**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " #### 4.1 算法流程图\n",
    "* 传统流程图 <br>\n",
    "传统流程图中矩形代表处理过程，菱形代表判断过程，以直线或折线确定各处理、判断过程的先后次序或形成循环。\n",
    "传统流程图的基本组件<br>\n",
    "![基本元素1](./Resources/flow-ele.png)\n",
    "基本组件组合成图<br>\n",
    "![传统流程图](./Resources/flow-demo.svg)\n",
    "* NS流程图<br>\n",
    "结构化流程图中，循环使用大框表达，判断使用三分框表达。增强了算法流程图的可读性。<br>\n",
    "NS流程图的基本元素<br>\n",
    "![基本元素2](./Resources/ns-ele.png)\n",
    "基本元素组合成图<br>\n",
    "![结构化流程图](./Resources/ns-demo.png)\n",
    "* PAD流程图<br>\n",
    "PAD流程图采用树型结构表达循环与判断，可用于表达`极其复杂`的程序设计<br>\n",
    "PAD流程图的基本元素<br>\n",
    "![基本元素3](./Resources/pad-ele.png)\n",
    "基本元素组合成图<br>\n",
    "![PAD流程图](./Resources/pad-demo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 伪代码\n",
    "**示例:课程质量统计**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    初始化`合格人数`:   $0 \\rightarrow p$<br>\n",
    "    初始化`不合格人数`: $0 \\rightarrow f$<br>\n",
    "    初始化`学生序号`:   $0 \\rightarrow s$<br>\n",
    "    while 学生序号 $s<100$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    读取第$s$个学生的成绩<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    if 成绩合格<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;        $p+1 \\rightarrow p$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    else<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;        $f+1 \\rightarrow f$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $s+1 \\rightarrow s$<br>\n",
    "    print $p$<br>\n",
    "    print $f$<br>\n",
    "    if $p>80$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    print 课程达标<br>\n",
    "    </p>\n",
    "    </div>\n",
    "    </div>\n",
    "    </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例一\n",
    "**求：** **$\\frac{1}{1\\times 2\\times 3 \\times 4\\times 5 \\cdots \\times 1000}$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法一，采用迭代的方式：**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    计算$\\frac{1}{1\\times 2}$<br>\n",
    "    将上一步的结果乘以$\\frac{1}{3}$<br>\n",
    "    将上一步的结果乘以$\\frac{1}{4}$<br>\n",
    "    将上一步的结果乘以$\\frac{1}{5}$<br>\n",
    "    将上一步的结果乘以$\\frac{1}{6}$<br>\n",
    "    一直写下去......<br>\n",
    "    将上一步的结果乘以$\\frac{1}{1000}$<br>\n",
    "    </p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法二, 使用循环并在循环中改变被乘数**\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    初始化结果:    $1 \\rightarrow r$<br>\n",
    "    初始化被乘数的倒数:    $ 1 \\rightarrow k$<br>\n",
    "    当  $k \\le 1000$ 如是：<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;计算$\\frac{r}{k}$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;令$r$为计算结果<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;令$k$加1<br>\n",
    "    否则&nbsp;&nbsp;输出$r$<br>\n",
    "    </p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将自然语言转化为流程图**<br>\n",
    "**方法二的流程图**<br>\n",
    "![方法二](./Resources/flow-1s.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将流程图转化为伪代码**<br>\n",
    "**示例:阶乘的倒数`伪码`**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    初始化`计算结果`:   $1 \\rightarrow r$<br>\n",
    "    初始化`计数变量`:   $1 \\rightarrow k$<br>\n",
    "    while $k \\le 1000$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $\\frac{r}{k} \\rightarrow r$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $k+1 \\rightarrow k$<br>\n",
    "    print $r$<br>\n",
    "    </p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将伪代码转化为C语言**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "double ifact_(int f){\n",
    "double r=1;\n",
    "int   k=1;\n",
    "while(k<=f){\n",
    "    r=r/k;\n",
    "    k=k+1;\n",
    "    }\n",
    "return r;\n",
    "}\n",
    "int main(){\n",
    "printf(\"%e\\n\",ifact_(20));\n",
    "return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例二\n",
    "**求：** **$1-\\frac{1}{3}+\\frac{1}{5}-\\frac{1}{7}+\\cdots$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法, 在循环中改变加数与符号**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    初始化结果:    $0 \\rightarrow r$<br>\n",
    "    初始化计数变量:    $ 1 \\rightarrow k$<br>\n",
    "    当  $k \\le 1000$ 如是：<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;计算$ \\frac{(-1)^{k+1}}{2k-1}$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;以上一步的结果增加$r$的值<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;令$k$加1<br>\n",
    "    否则&nbsp;&nbsp;输出$r$<br>\n",
    "    </p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将自然语言转化为流程图**<br>\n",
    "**例二的流程图**<br>\n",
    "![方法二](./Resources/flow-2s.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将流程图转化为伪代码**<br>\n",
    "**示例:例二`伪码`**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    初始化`计算结果`:   $0 \\rightarrow r$<br>\n",
    "    初始化`计数变量`:   $1 \\rightarrow k$<br>\n",
    "    初始化`符号变量`:   $1 \\rightarrow s$<br>\n",
    "    while $k \\le 1000$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $-1 \\times s \\rightarrow s$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $r+\\frac{s}{2k-1} \\rightarrow r$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;    $k+1 \\rightarrow k$<br>\n",
    "    print $r$<br>\n",
    "    </p></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**示例:例二`源码`**<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "void demo_2(){\n",
    "long k=1;\n",
    "double r=0.0;\n",
    "double s=-4.0;\n",
    "while(k<=100000000){\n",
    "s*=-1;\n",
    "r+=s/(2*k-1);\n",
    "k++;\n",
    "if(k%10000000==0) printf(\"%01.25lf\\n\",r);\n",
    "}\n",
    "}\n",
    "int main(){\n",
    "demo_2();\n",
    "}   \n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例三\n",
    "**判断一个数$k$是否为素数**<br>\n",
    "**方法：** &nbsp;&nbsp;查看2到$\\frac{k}{2}$中的任意一个数是否能整除$k$?<br>\n",
    "**用自然语言表达步骤**<br>\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    输入被除数:    $k$<br>\n",
    "    初始化被除数为:    $2$<br>\n",
    "    当被除数小于等于$\\frac{k}{2}$ 如是：<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;检查除数能否整除$k$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;能？$k$不是素数<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;被除数加一<br>\n",
    "    $k$是素数<br>\n",
    "    </p></div></div></div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将自然语言转化为流程图**<br>\n",
    "**例三的流程图**<br>\n",
    "![方法二](./Resources/flow-3.svg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将流程图转化为伪代码**\n",
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    输入被除数:    $k$<br>\n",
    "    初始化被除数:    $2 \\rightarrow t$<br>\n",
    "    初始化结果:    $-1 \\rightarrow r$<br>\n",
    "    while &nbsp;&nbsp;$t \\le \\frac{k}{2}$ <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;&nbsp;$k\\mod d=0$<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$0 \\rightarrow r$,输出r<br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;$t+1 \\rightarrow t$<br>\n",
    "    输出r<br>\n",
    "    </p></div></div></div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**将伪代码转化为源码**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <stdio.h>\n",
    "#include <math.h>\n",
    "#include <stdio.h>\n",
    "int isPrime(unsigned int k){\n",
    "for(int t=2;t<=k/2;t++){\n",
    "if(k%t==0) return 0;\n",
    "}\n",
    "return -1;\n",
    "}\n",
    "int main(){\n",
    "for(int k=1;k<100;k++)\n",
    "if(isPrime(k)) printf(\"%d\\n\",k);\n",
    "return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题：<br>\n",
    "1. **编写程序求**$1+\\frac{1}{1!}+\\frac{1}{2!}+\\frac{1}{3!} +\\cdots$ <br>\n",
    "2. **编写程序求**$\\frac{1}{1^2}+\\frac{1}{2^2}+\\frac{1}{3^2}+\\cdots$ <br>\n",
    "3. **编写程序求：**$\\sqrt{r}$<br>\n",
    "4. **使用习题3的程序改良素数判断程序**<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
